The present invention generally relates to digital circuits, and, more particularly, to a binary multiplier circuit.
With the advent of technologies that require complex and fast data processing, digital systems have evolved to perform large numbers of mathematical operations in lesser time. Since multiplication is the most basic form of mathematical operation performed by a digital system, different algorithms, such as Booth's multiplication algorithm, have been developed to reduce the time for a digital system to multiply two numbers.
Booth's multiplication algorithm performs multiplication based on shift and add operations. A conventional Booth's multiplier circuit includes a multiplexer or mux, an accumulator, and a binary shifter. Bits of a multiplicand are provided to a first input terminal of the mux. A second input terminal of the mux receives binary zero as input. Bits of a multiplier are provided serially to a select input terminal of the mux by right-shifting and providing the least significant bit (LSB) first. Inputs at the first and second input terminals of the mux are selected based on the bits provided at the select input terminal thereof. The mux output is provided to the accumulator. The multiplicand is added to a previous intermediate result stored in the accumulator for bits of the multiplier that are set to binary one and the result is right-shifted. The previous intermediate result is right-shifted, without the addition of the multiplicand, for the bits of the multiplier that are set to binary zero.
Since the intermediate result stored in the accumulator needs to be shifted for each bit of the multiplier, generating a final result requires a count of clock cycles equal to the bit-length of the multiplier, irrespective of a value of the bit. Thus, 8 clock cycles are required for multiplying an 8-bit multiplier and multiplicand and 16 clock cycles are required for multiplying a 16-bit multiplier and multiplicand. The number of clock cycles, and therefore the time required for multiplication increases in direct proportion to the bit-length of the multiplier, which limits the performance of the conventional Booth multiplier.
It would be advantageous to have a multiplier circuit that is fast, consumes fewer clock cycles, and that overcomes the above-mentioned limitations of conventional multiplier circuits.